package com.cheng.algorithm.sort;

import java.util.Arrays;

/**
 * @User Administrator
 * @Classname HeapSort
 * @Project Data-structure-and-algorithm
 * @Description 堆排序代码实现
 * 堆排序基本介绍：
 * 1)堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
 * 2)堆是具有以下性质的完全二叉树:
 * 3)每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆,注意:没有要求结点的左孩子的值和右孩子的值的大小关系。
 * 大顶堆特点: arr[i] >= arr[2*i+1]&&arr[i>=arr[2*i+2]  i对应第几个节点i从0开始编号
 * 4)每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
 * 小顶堆特点: arr[i]<=arr[2*i+1]&&arr[i]<= arr[2*i+2]  i对应第几个节点，i从0开始编号
 * 5)升序采用大顶堆，降序采用小顶堆
 * 堆排序基本思想：以大顶堆排序为例：
 * 1）将待排序序列构造成一个大顶堆，构造顺序：从左到右，从下到上
 * 2)此时，整个序列的最大值就是堆顶的根节点。
 * 3)将其与堆（完全二叉树）末尾元素进行交换，此时堆末尾就为最大值。把这个最大值放到一边
 * 4)然后将剩余n-1个元素重新构造成一个堆（完全二叉树），这样会得到n个元素的倒数第二小的值。如此反复执行，便能得到一个有序序列了。
 * 可以看到在依次构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了.
 * @Author wpcheng
 * @Create 2021-08-31-10:40
 * @Version 1.0
 */
public class HeapSort {
    public static void main(String[] args) {

        int[] arr = {4, 6 , 8, 5, 9};
        heapSort(arr);
    }
    //堆排序方法
    public static void heapSort(int[] arr){
        int temp = 0;
        //调用adjustHeap方法，构建一个完整的大顶堆
        for (int i = arr.length / 2 - 1; i >= 0 ; i--) {
            adjustHeap(arr,i, arr.length);
        }
        //上面构建完大顶堆后，根据大顶堆的性质，堆顶元素（arr[0]）为最大值，循环交换对顶元素和堆末尾（树对应数组末尾）元素
        for (int j = arr.length - 1; j > 0 ; j--) { //j初始值为数组末尾元素
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr,0,j);
        }
        System.out.println("排序后："+ Arrays.toString(arr));
    }

    /**
     * 将数组构建成大顶堆的方法
     * @param arr 构建大顶堆的数组，
     * @param i 非叶子节点在数组中的索引，以该非叶子节点构建大顶堆
     *          如 i = 1 时，即非叶子节点为 6，构建的大顶堆用数组来表示为：{4, 9 , 8, 5, 6}
     * @param length 构建成的大顶堆的节点个数
     */
    public static void adjustHeap(int[] arr,int i,int length){
        int temp = arr[i];//保存当前节点的值
        //用for循环找到最大值并交换
        //k初始指向 i对应节点的左子节点，步长为下一个左子节点
        for (int k = i * 2 + 1; k <length ; k = k * 2 +1) {
            //当节左子节点小于右子节点时
            if (k + 1 < length && arr[k] < arr[k+1]){
                k = k + 1; //让k指向右子节点
                //如果子节点大于父节点
            }if (arr[k] > temp){
                arr[i] = arr[k];//父节点（i对应节点）上的值替换为最大值arr[k]
                i = k;//下标也进行交换
            }else {
                break;
            }
        }
        //当退出for循环后，已经把最大值arr[k]放到了最顶（i对应节点），把原来i对应节点的值放到arr[k]原来的位置
        arr[i] = temp;//这时候的i和最初的i已然不同
    }

}
